// @algorithm @lc id=240 lang=cpp 
// @title search-a-2d-matrix-ii


// @test([[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],5)=true
// @test([[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],20)=false
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int row = m - 1, col = 0;
        while(0 <= row && col < n){
            if(target < matrix[row][col])
                -- row;
            else if(matrix[row][col] < target)
                ++ col;
            else
                return true;
        }
        return false;
    }
};